Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

  1. A:          a1 → a2
  2.                    ↘
  3.                      c1 → c2 → c3
  4.                    ↗            
  5. B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

  • If the two linked lists have no intersection at all, return null.
  • The linked lists must retain their original structure after the function returns.
  • You may assume there are no cycles anywhere in the entire linked structure.
  • Your code should preferably run in O(n) time and use only O(1) memory.

Solution:

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode(int x) {
  7.  *         val = x;
  8.  *         next = null;
  9.  *     }
  10.  * }
  11.  */
  12. public class Solution {
  13.   public ListNode getIntersectionNode(ListNode l1, ListNode l2) {
  14.     if (l1 == null || l2 == null) return null;
  16.     // step 1. count the two lists
  17.     int n1 = count(l1), n2 = count(l2);
  19.     // step 2. move the longer one |n2 - n1| steps
  20.     int n = Math.abs(n1 - n2);
  22.     while (n-- > 0) {
  23.       if (n1 > n2) 
  24.         l1 = l1.next;
  25.       else
  26.         l2 = l2.next;
  27.     }
  29.     // step 3. move together and find the meeting point
  30.     while (l1 != l2) {
  31.       l1 = l1.next;
  32.       l2 = l2.next;
  33.     }
  35.     return l1;
  36.   }
  38.   int count(ListNode l) {
  39.     if (l == null) return 0;
  40.     return 1 + count(l.next);
  41.   }
  42. }